1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <cstdio>
#include <map>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
LL p, w[maxn]; int n, Q;
const int maxP = 5e4 + 5;
vector <LL> prime; bool if_p[maxP];
void ins(){
for (int i = 2; i < maxP; i++){
if (!if_p[i]) prime.push_back(1ll * i);
for (int j = 0; i * prime[j] < maxP && j < prime.size(); j++){
if_p[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
LL phi(LL x){
LL res = x;
for (int i = 0; i < prime.size() && prime[i] * prime[i] <= x; i++){
if (x % prime[i] == 0){
res = res - res / prime[i];
while (x % prime[i] == 0) x /= prime[i];
}
}
if (x != 1) res = res - res / x;
return res;
}
LL pow(LL x, LL t, LL mo){
LL res = 1; if (x > mo) x = x % mo + mo;
while (t > 0){
if (t & 1){
res = res * x;
if (res > mo) res = res % mo + mo;
}
x = x * x;
if (x > mo) x = x % mo + mo;
t >>= 1;
}
return res;
}
LL calc(int cur, int r, LL mo){
if (cur == r) return w[cur];
if (mo == 1) return 1;
LL tmp = calc(cur + 1, r, phi(mo));
if (tmp <= phi(mo)) return pow(w[cur], tmp, mo);
return pow(w[cur], tmp + phi(mo), mo);
}
int main(){
ins();
scanf("%d%lld", &n, &p);
for (int i = 1; i <= n; i++) scanf("%lld", w + i);
scanf("%d", &Q);
while (Q--){
int l, r; scanf("%d%d", &l, &r);
printf("%lld\n", calc(l, r, p) % p);
}
return 0;
}
|